//题目:
// 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。
// 实现一种方法，计算小孩有多少种上楼梯的方式。
// 结果可能很大，你需要对结果模1000000007。
#include<iostream>

using namespace std;
//代码
class Solution 
{
    int arr[1000001]={0};//记忆化搜索
public:
    int dfs(int n)
    {
        if(n==1 || n==2)return n;
        if(n==3)return 4; 

        if(arr[n]!=0)return arr[n];

        int ret=((dfs(n-1)+dfs(n-2))%1000000007+dfs(n-3))%1000000007;

        arr[n]=ret;
        return ret;
    }
    int waysToStep(int n) 
    {
        //法一：回溯+记忆化搜索
        // return dfs(n);

        //法二：动态规划
        //1.创建dp表————dp[i]表示：上到第i级台阶的所有方式种数
        int dp[1000001]={0};
        // int* dp = new int[1000001]{ 0 };

        //2.初始化
        dp[1]=1;dp[2]=2;dp[3]=4;

        //3.填表
        for(int i=4;i<1000001;i++)
            dp[i]=((dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;

        //4.返回
        return dp[n];
    }
};